import java.util.Arrays;

public class Algorithm {
    /*
    public static void main(String[] args) {
        int[] arr = {27,58,32,103,76,66,89,55,99,106,94,46};
        //Sort.mergeSort(arr);
        //Sort.quickSort(arr);
        //Sort.heapSort(arr);
        Sort.radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
     */
    public static void main(String[] args) {
        System.out.println("Today I'm gonna crazy!!!!brain storm!!!");
    }
}

class Sort {
    public static void swap(int[] arr, int p, int q) {
        int t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }

    public static void mergeSort(int[] arr) {
        processOfMergeSort(arr, 0, arr.length - 1);
    }

    public static void processOfMergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l)>>1);
        processOfMergeSort(arr, l, mid);
        processOfMergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int p1 = l, p2 = mid + 1, i = 0;
        while (p1 <= mid && p2 <= r) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length;i++) {
            arr[l + i] = help[i];
        }

    }

    public static void quickSort(int[] arr) {
        processOfQuickSort(arr, 0, arr.length - 1);
    }

    public static void processOfQuickSort(int[] arr, int l, int r) {
        if (l < r) {
            swap(arr, r,l + (int)(Math.random() * (r - l + 1)));
            int[] p = partition(arr, l, r);
            processOfQuickSort(arr, l, p[0] - 1);
            processOfQuickSort(arr, p[1] + 1, r);
        }
    }

    public static int[] partition(int[] arr, int l, int r) {
        int less = l - 1, more = r;
        while (l < more) {
            if (arr[l] < arr[r]) {
                swap(arr, l++, ++less);
            } else if(arr[l] > arr[r]) {
                swap(arr, l, --more);
            } else {
                l++;
            }
        }
        swap(arr, more ,r);
        return new int[]{less + 1, more};
    }

    public static void heapSort(int[] arr) {
        processOfHeapSort(arr);
    }

    public static void processOfHeapSort(int[] arr) {
        for (int i = 0; i < arr.length;i++) {
            heapInsert(arr, i);//把堆里面的每个位置的数字都进行大根堆化
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);//堆化
            swap(arr, 0, --heapSize);
        }
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1: left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void radixSort(int[] arr) {
        processOfRadixSort(arr, 0, arr.length - 1, maxDigit(arr));
    }

    public static int maxDigit(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length;i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    public static void processOfRadixSort(int[] arr, int l, int r, int digit) {
        final int radix = 10;
        int[] bucket = new int[r - l + 1];
        int i, j;
        for (int d = 1; d <= digit;d++) {
            int[] count = new int[radix];
            for (i = l; i <= r;i++) {//获得每位数字的词典
                j = getDigit(arr[i], d - 1);
                count[j]++;
            }

            for (i = 1; i < radix;i++) {//前缀和
                count[i] = count[i] + count[i-1];
            }

            for (i = r; i >= l;i--) {
                j = getDigit(arr[i],  d - 1);//先获得每位数
                bucket[count[j] - 1] = arr[i];//在词典里面找到这个数，放在桶里面
                count[j]--;
            }
            for (i = l, j = 0;i <= r;i++, j++) {
                arr[i] = bucket[j];//把桶里面的元素导出来
            }
        }
    }

    public static int getDigit(int num, int d) {
        return num / (int)(Math.pow(10,d)) % 10;
    }
}

/*
   public boolean isPalindrome(ListNode head) {
        boolean res = true;
        ListNode fast = head;
        ListNode slow = head;

        while (fast.next != null && fast.next.next != null) {//find the mid
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode p1 = slow;
        ListNode p2 = slow.next;
        ListNode p3 = null;
        p1.next = null;
        while (p2 != null) {
            p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
        }
        p3 = p1;//remember the last node
        p2 = head;//head
        while (p2 != null && p1 != null) {
            if(p2.val != p1.val) { head to mid ~ last to mid
                res = false;
                break;
            }
            p2 = p2.next;
            p1 = p1.next;
        }
        p1 = p3.next;//the prev of last one
        p3.next = null;//last one point ot null
        while (p1 != null) {
            p2 = p1.next;//remember the next of p1
            p1.next = p3;//reverse the node
            p3 = p1;
            p1 = p2;
        }

        return res;
    }
 */


    /*
     ListNode sH = null, sT = null;
            ListNode eH = null, eT = null;
            ListNode mT = null, mH = null;
            ListNode next = head;
            while (head != null) {
                next = head.next;
                head.next = null;
                if (head.val < x) {

                    if (sH == null) {
                        sH = head;
                        sT = head;
                    } else {
                        sT.next = head;
                        sT = head;
                    }

                } else if (head.val == x) {

                    if (eH == null) {
                        eH = head;
                        eT = head;
                    } else {
                        eT.next = head;
                        eT = head;
                    }

                } else {
                    if (mH == null) {
                        mH = head;
                        mT =head;
                    } else {
                        mT.next =head;
                        mT = head;
                    }
                }
                head = next;

            }
            if (sT != null) {
                sT.next = eH;
                eT = eT == null ? sT : eT;
            }

            if (eT != null) {
                eT.next = mH;
            }
            return sH != null ? sH :(eH != null ? eH : mH);
 */

/*
public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode smallHead = small;
        ListNode large = new ListNode(0);
        ListNode largeHead = large;
        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                large.next = head;
                large = large.next;
            }
            head = head.next;
        }
        large.next = null;
        small.next = largeHead.next;
        return smallHead.next;
    }
 */

